package 牛客.查找;/*
 *@Author: helen
 *@Date:   2021/4/19 15:51
 *@Description:
题目描述
    给出一个整数数组，请在数组中找出两个加起来等于目标值的数，
    你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。
    注意：下标是从1开始的
    假设给出的数组中只存在唯一解
    例如：
        给出的数组为 {20, 70, 110, 150},目标值为90
        输出 index1=1, index2=2
        示例1
            输入    [3,2,4],6
            返回值  [2,3]
 */


import java.util.HashMap;

public class 两数之和 {
    //暴力法：时间复杂度O（n^2）   空间复杂度O（1）
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i+1; j < numbers.length; j++) {
                if(target == numbers[i] + numbers[j]){
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return null;
    }

    //使用HashMap，时间复杂度O（n）   空间复杂度O（n）
    public int[] twoSum02 (int[] numbers, int target) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int temp = target - numbers[i];
            if(map.containsKey(temp))
                return new int[]{map.get(temp) + 1, i + 1};
            map.put(numbers[i], i);
        }
        return null;
    }

    public static void main(String[] args) {
        两数之和 obj = new 两数之和();
        int num[] = {3,2,4};
        int target = 6;
        //int[] result = obj.twoSum(num, target);
        int[] result = obj.twoSum02(num, target);
        for (Integer i: result) {
            System.out.print(i + " ");
        }
    }
}
